package org.basis.algorithm.promote;

import java.util.ArrayDeque;

/**
 * 岛问题
 *
 * @author Mr_wenpan@163.com 2022/01/05 15:56
 */
public class Islands {

    public static void main(String[] args) {
        int[][] m1 = {{0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 1, 1, 0, 1, 1, 1, 0},
                {0, 1, 1, 1, 0, 0, 0, 1, 0},
                {0, 1, 1, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 1, 0, 0},
                {0, 0, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},};
        System.out.println(countIslands(m1));

        int[][] m2 = {{0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 1, 1, 1, 1, 1, 1, 0},
                {0, 1, 1, 1, 0, 0, 0, 1, 0},
                {0, 1, 1, 0, 0, 0, 1, 1, 0},
                {0, 0, 0, 0, 0, 1, 1, 0, 0},
                {0, 0, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},};
        System.out.println(countIslands(m2));
        String s = smallestSubsequence("cbacdcbc");
        System.out.println(s);

    }

    public static String smallestSubsequence(String s) {

        if (s == null || s.length() <= 1) {
            return s;
        }

        char[] chars = s.toCharArray();
        // 单调递增的栈
        ArrayDeque<Character> stack = new ArrayDeque<Character>();
        // 记录每个字符的出现次数(由于全是小写字母，所以26个长度就够了)
        int[] count = new int[26];
        for (int i = 0; i < chars.length; i++) {
            // 获取当前字符在数组中的位置
            int index = chars[i] - 'a';
            // 出现次数++
            count[index]++;
        }

        for (int j = 0; j < chars.length; j++) {
            while (!stack.isEmpty()
                    && stack.peekLast() >= chars[j]
                    && count[stack.peekLast() - 'a'] > 1) {
                stack.pollLast();
                count[chars[j] - 'a']--;
            }
            // 将i位置的字符加入栈
            stack.addLast(chars[j]);
        }

        StringBuilder sb = new StringBuilder();

        while (!stack.isEmpty()) {
            sb.append(stack.pollFirst());
        }

        return sb.toString();
    }


    /**
     * 统计一个二维矩阵中有多少个岛
     *
     * @param m 二维矩阵
     * @return int 岛的数量
     */
    public static int countIslands(int[][] m) {
        if (m == null) {
            return 0;
        }
        int res = 0;
        // 二维矩阵一共 i 行
        for (int i = 0; i < m.length; i++) {
            // 二维矩阵一共j列
            for (int j = 0; j < m[0].length; j++) {
                // 这个位置的数字为1时，说明这里有一片岛，从这个位置开始取感染他能直接接触到的上下左右
                if (m[i][j] == 1) {
                    res++;
                    infect(m, i, j, m.length, m[0].length);
                }
            }

        }
        return res;
    }

    /**
     * 感染函数
     *
     * @param m     二维矩阵
     * @param i     第i行
     * @param j     第j列
     * @param line  行边界
     * @param colum 列边界
     * @author Mr_wenpan@163.com 2022/1/5 4:05 下午
     */
    private static void infect(int[][] m, int i, int j, int line, int colum) {
        // 递归出口，不满足条件立即退出
        if (i < 0 || i >= line || j < 0 || j >= colum || m[i][j] != 1) {
            return;
        }
        // 如果该位置是1，那么就把该位置改为2，然后递归感染他的上下左右
        m[i][j] = 2;
        infect(m, i + 1, j, line, colum);
        infect(m, i, j + 1, line, colum);
        infect(m, i - 1, j, line, colum);
        infect(m, i, j - 1, line, colum);
    }

}
